package com.yuqian.JavaSe.leetcode.easy;

/**
 * given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]
 * @author yuqian
 *
 */
public class MoveZeroes {


	 public static void main(String[] args) {
		int[] kk = {0,1,0,3,12};
		moveZeroes1(kk);
		  for(int o =0;o<kk.length;o++){
			  System.out.print(kk[o]+",");
		  }
	}

	 /**
	  * 每次找出第一个0和第一个不是0的进行交换
	  * @param nums
	  */
	 public static void moveZeroes1(int[] nums) {
	        if(nums==null||nums.length==0){
	        }else{
	            //记录下次循环开始的地方
	            int m=0;
	            int n= nums.length;
	            for(int o =0;o<n;o++){
	                //记录第一个0的位置
	                int k=-1;
	                for(;m<n;m++){
	                //如果已找到第一个为0的位置且当时的数字不是0则交换
	                   if(k!=-1&&nums[m]!=0){
	                        nums[k] = nums[m];
	                        nums[m] = 0;
	                        m=k+1;
	                        break;
	                    }
	                    //判断第一个为0的数组下标
	                    if(k==-1&&nums[m]==0){
	                        k=m;
	                    }
	                 
	                }
	            }
	        }
	    }

/**
 * 找到第一个为0的地方m，找到不是0的数字交换，那么接下来第一个为0的地方即为m+1;重复以上步骤
 * @param nums
 */
public static void moveZeroes2(int[] nums) {
     if(nums==null||nums.length==0){
     }else{
         //记录下次循环开始的地方
         int m=-1;
         int n= nums.length;
         for(int o =0;o<n;o++){
        	//判断第一个为0的数组下标
            if(m==-1&&nums[o]==0){
                 m=o;
                 continue;
             }
             
             if(m==-1||nums[o]==0){
             	continue;
             }
             nums[m] = nums[o];
             nums[o] = 0;
             //下一个为0的下表
             m = m+1;
         }
     }
 }

/**
 * 这个方法特别好而且效率很高，很简洁
 * 具体思路是：
 * 先把所有不是0的按顺序插入到数组，然后把后面全部插入0
 * @param nums
 */
   	public void moveZeroes3(int[] nums){
   		int index=0;
   		for (int i=0;i<nums.length;i++){
   			if (nums[i]!=0) nums[index++]=nums[i];
   		}
   		while(index<nums.length){
   			nums[index++]=0;
   		}
   	}
}
